'''
https://leetcode.cn/problems/find-the-celebrity
'''
from functools import cache


# The knows API is already defined for you.
# return a bool, whether a knows b
def knows(a: int, b: int) -> bool:
    return False

class Solution:
    def findCelebrity(self, n: int) -> int:
        indegree = [0] * n
        outdegree = [0] * n
        for a in range(n):
            for b in range(n):
                if a == b: continue
                if knows(a, b):
                    indegree[b] += 1
                    outdegree[a] += 1
        for i, c in enumerate(indegree):
            if c == n-1 and outdegree[i] == 0:
                return i
        return -1

    def findCelebrity2(self, n: int) -> int:
        @cache
        def know(a, b):
            return knows(a, b)
        # 候选者一定没有认识的人
        celebrity_candidate = 0
        for v in range(1, n):
            if know(celebrity_candidate, v):
                celebrity_candidate = v
        # is he celebrity?
        # 他不认识所有人，所有人认识他
        for u in range(n):
            if u == celebrity_candidate:
                continue
            if not know(u, celebrity_candidate) or know(celebrity_candidate, u):
                return -1
        return celebrity_candidate